查找

发表于 | 更新于: | 分类于
字数统计: 1,255 字

1 查找的基本概念

  1. 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
  2. 查找表：用于查找的数据集合称为查找表
  3. 静态查找表：如果一个查找表的操作不涉及修改或删除称为静态查找表
  4. 动态查找表：需要动态删除或插入的查找表称为动态查找表
  5. 关键字：数据元素中唯一标识该元素的数据项的值称为关键字
  6. 平均查找长度：所有查找过程进行关键字比较次数的平均值

2 顺序查找和折半查找

2.1 顺序查找

  1. 一般线性表的顺序查找
    思想：在线性表一头设置哨兵，从另外一头开始逐个检测关键字是否满足查找条件
    1
    2
    3
    4
    5
    6
    7
    8
    9
    typedef struct{                            //查找表的数据结构
        ElemType *elemm;
        int TableLen;
    }SSTable;
    int Search_Seq(SSTable ST,ElemType key){
        ST.elem[0]=key;                         //哨兵
        for(i=ST.TableLen;ST.elem[i]!=key;i--) ; //从后往前找，找不到直接跳过
        return i;                               //若i为0表示查找失败
    }

查找成功的平均查找长度：(n+1)/2;
查找不成功时的平均查找长度：n+1；

2.2 折半查找

折半查找又称为二分查找，仅适用于有序的顺序表。
算法思想：将key与表中间元素比较，若相对查找 成功；若不等，则依据大小关系往前半部分或后半部分查找；如此重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
int Binary_Search(SeqList L,ElemType key){
    int low=0;high=L.TableLen-1;mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]==key)        //找到则返回
            return mid;
        else if(L.elem[mid]>key)    //往前找
            high=mid-1;
        else                        //往后找
            low=mid+1;
    }
    return -1;                      //找不到返回-1
}

时间复杂度：O(log2n);

分块查找

分块查找基本思想：将查找表分成若干子块，块间有序而块内元素无序。建立索引表，索引表的内容是：各块的最大关键字和该块的第一个元素地址的映射关系。
查找步骤：先用顺序查找或折半查找确定块，再在块内查找。

3 B树和B+树

3.1 B树及其基本操作

B树又称为多路平衡查找树，m阶B树或为空树或满足以下特性：

  • 树中每个结点至多有m-1个结点，m棵子树；
  • 若根结点不是终端结点，则至少有两棵子树
  • 根结点以外的非叶结点至少有⌈m/2⌉棵子树，⌈m/2⌉-1个关键字
  • 所有非叶结点由：关键字个数、关键字和指向子树根结点的指针组成
  • 所有叶结点出现在同一层且不带任何信息(即NULL)
  1. B树的高度
    logm(n+1)<=h<=log⌈m/2⌉((n+1)/2)+1;
  2. B 树的查找
    查找步骤：1.在B树中找结点；2.在结点中找关键字
  3. B树的插入
    插入需要修改B树结构使符合B树定义(涉及结点的分裂)
  4. B树的删除
    删除操作需要修改B树的结构使其符合B树定义(涉及结点的合并)

3.2 B+树基本概念

m阶B+树满足：

  • 每个分支结点至多有m棵子树
  • 非叶的根结点至少有两棵子树，其它分支结点至少有⌈m/2⌉棵子树
  • 结点的关键字数目和子树数目相等
  • 所有叶结点包含全部关键字和指向记录的指针
  • 所有分支结点只包含它的各子结点中关键字的最大值和指向子结点的指针

4 散列表(Hash)

4.1 散列表的基本概念

散列函数：把查找表中的关键字映射到该关键字对应的地址的函数称为散列函数，记为Hash(key)=Addr。
冲突：散列函数中把两个或以上的关键字映射到同一地址。
散列表：存储关键字和存储地址的直接映射关系。

4.2 散列函数的构造方法

  1. 直接定址法

    H(key)=a*key+b
  2. 除留余数法

    H(key)=key%p
  3. 数字分析法
  4. 平法取中法
  5. 折叠法

4.3 冲突处理方法

  1. 开发定址法

    Hi=(H(key)+di)%m

    其中m为散列表表长，di为增量序列。
    di通常有四种取法：
    线性探测法 ：di=1,2,3…,m-1
    平法探测法 ： di=12,-12,22,-22,…,k2,-k2
    再散列法：di=Hash2(key)
    伪随机序列法：di为伪随机序列
  2. 拉链法
    将所有冲突的关键字存储在一个线性链表中

4.4 散列查找及性能分析

散列表的查找效率取决于：散列函数、冲突处理方法和填装因子。
填装因子：填装因子=(表中记录数)/(散列表长度)